The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
Enterprises that host or manage large networks, such as Internet service providers (ISPs), commonly deploy virtual private networks (VPNs) so that ISP customers can securely communicate private data across non-secure semi-public Internet nodes. An ISP network comprising provider edge (PE) routers, core network routers, and other elements may be termed an autonomous system (AS). Such systems commonly use Border Gateway Protocol (BGP), as defined in Request for Comments (RFC) 1771 of the Internet Engineering Task Force (IETF), for exchanging route information (“prefixes”) and reachability information with other systems.
Current practices provide no effective way for managers of BGP VPNs to determine or account for transit costs of traffic passing through a service provider. In addition, the transit cost between multiple autonomous systems also is not considered. Thus, current practices provide no effective way for any customer edge (CE) router to find the shortest path for a prefix with multiple paths traversing several autonomous systems within the same administrative domain.
For the purpose of illustrating one relevant problem, FIG. 1 is a block diagram of an example network configuration. A customer network 102 has a CE router 104 that is coupled by link 105 to a PE router 106 associated with an ISP core network 109. PE router 106 is coupled by link 114 through ISP core network 109 to a second PE router 108, which is linked to CE router 110 by link 116. The second CE router 110 is associated with a separate customer network 112 of a different customer of the ISP. PE routers 106, 108 and core network 109 are associated with one ISP 120. Thus, in FIG. 1 the first and second CE routers 104, 110 are connected indirectly via a common ISP 120. CE router 104 and PE router 106 could run either BGP (and either exterior BGP [EBGP] or interior BGP [IBGP]) or an interior gateway protocol (IGP) over link 105. Similarly, PE routers 106, 108 on link 114, and PE router 108 and CE router 110 on link 116 could run any of IBGP and IGP.
In this scenario, for a route that is originated by CE router 104, and reaches CE router 110 via PE routers 108, 106, CE router 110 currently has no way to calculate the total cost for it to reach CE router 104. Generally, there is currently no way to calculate a total cost value that reflects cost values that are developed independently by different routing protocols, and there is no way to do so between EBGP and IGP in particular.
Having a way to compute total link cost or transit cost between different routing protocols would be particularly useful when there are different routing paths available via different routing protocols, or the same routing protocols, running under the same administrative domain. For example, a customer of multiple service providers may wish to select the shortest path for a given route automatically. Currently, no automatic selection mechanism exists, and path selection, in this case, is performed by manual configuration.
No other solutions that attempt to resolve this problem are known. One cost communication mechanism, which does not solve the problem identified herein, is described in Retana et al., in the document named “draft-retana-bgp-custom-decision-00.txt,” available at the IETF web site and Internet-draft archive sources. Retana et al. propose a mechanism for extending community attributes to carry a cost of a route within one BGP domain or autonomous system. When route information is communicated outside an AS, the cost value is lost. Thus, the mechanism of Retana et al. cannot be used to transport a cost of a route across the boundaries of autonomous systems.